/***************************************************************************
													mstl.h	-  Mini-STL library
														 -------------------
		begin 							 : Mon May 6 2002
		copyright 					 : (C) 2002 by Michiel Visser
		email 							 :
 ***************************************************************************/

/***************************************************************************
 *																																				 *
 *	 This program is free software; you can redistribute it and/or modify  *
 *	 it under the terms of the GNU General Public License as published by  *
 *	 the Free Software Foundation; either version 2 of the License, or		 *
 *	 (at your option) any later version.																	 *
 *																																				 *
 ***************************************************************************/

//---------------------------------------------------------------------------
#ifndef __MSTL_ALLOC_H__
#define __MSTL_ALLOC_H__
//---------------------------------------------------------------------------

#include "mstl_dbg.h"

#if !defined(MALLOC_FREE_TEST) && !defined(MALLOC_COUNT) && !defined(MALLOC_BOUNDARY_TEST)
#define mstl_alloc(s) _mstl_alloc(s,__FILE__,__LINE__)
inline void *_mstl_alloc( size_t s, char *f, int l) { return malloc(s); }
inline void mstl_free( void *p) { free(p); }
#else
void *mstl_alloc( size_t s);
void mstl_free( void *p);
#endif

/// placement new operator (uses existing memory pointed by ptr).
inline void * operator new	 (size_t s, void *ptr)	{ return ptr; }
/// placement new[] operator (uses existing memory pointed by ptr).
inline void * operator new[] ( size_t s, void *ptr)  { return ptr; }
inline void operator delete(void*,void *) { return; }

inline void * operator new	 ( size_t s) { return mstl_alloc(s); }
inline void * operator new[] ( size_t s) { return mstl_alloc(s); }

inline void operator delete(void *p) { mstl_free(p); }

inline void operator delete[](void *p) { mstl_free(p); }

inline void *reserveBytes(int num ) { return mstl_alloc(num); }
template<typename T> inline void *reserveBytes(int num ) { return mstl_alloc(num);}

template<typename T> inline void freeBytes(void *v ) { mstl_free(v); }
template<typename T> inline void freeObject(T *p) { p->~T();freeBytes<T>(p); }


template<typename T> struct Create
{ static T * fromSpace(void *space) { return new (space) T(); }
	template<typename S> static T *fromSpace(void *space, const S &param) { return new (space) T(param); }
	template<typename S> static T *aNew(const S &param) { return new (reserveBytes<T>(sizeof(T))) T(param); }
	static T *aNew() { return new (reserveBytes<T>(sizeof(T))) T(); }
	static T *aNewArray(int count) { return new T[count]; }
};

namespace MSTL
{

template<int ElemSize_i, int ClusterCount_i, int ClusterSize_i> struct BasicClustering
{ /* tyle code for calculating clusterSize given elemsize and clustercount
	elemSize=8; clusterSizes={256,512,1024,2048,4096};
	spaceInCluster=?((($-4)/elemSize)*elemSize);
	clusterCount=?(256*1024)/$;
	meanOverhead=?($+($-spaceInCluster!)*clusterCount!);
	totalSpace=?spaceInCluster!*clusterCount!;
	meanEfficiency=? (0.0+meanOverhead!)/totalSpace!;
	clusterSizes:!meanEfficiency!
	//this gives optimum for elemsize=12: clusterSize=1024
	//for elemSize=8: clusterSize=2048
	*/
	enum 
	{ ClusterSize 				= ClusterSize_i,
		ClusterCount				= ClusterCount_i,
		ElemsInClusterCount = ((ClusterSize-sizeof(void *))/ElemSize_i),
		TotalElemCount			= ElemsInClusterCount*ClusterCount,
		elemOffset					= 4
	};
	typedef char Elem[ElemSize_i];
	typedef struct
	{ void *m_allocBlock;
		Elem m_elems[ElemsInClusterCount];
		//void init() {}
	} Cluster;
};

template<int ElemSize_i, int ClusterCount_i, int ClusterSize_i, int ElemsInClusterCount_i> struct GCClustering
{ 
/* How to calculate ElemsInClusterCount:
Minimize:
clusterSpaceLeft = ? ClusterSize - ( 4 + $*ElemSize + 4*(($+32)/32) );
For ClusterSize=2048, ElemSize=8: ElemsInClusterCount=251

*/
	typedef char Elem[ElemSize_i];
	enum 
	{ ClusterSize 				= ClusterSize_i,
		ClusterCount				= ClusterCount_i,
		ElemsInClusterCount = ElemsInClusterCount_i,
		TotalElemCount			= ElemsInClusterCount*ClusterCount,
		elemOffset					= 4+4*((ElemsInClusterCount+32/*31+dirty bit*/)/32)
	};
	typedef struct
	{ void *m_allocBlock;
		unsigned int m_paintBits[(ElemsInClusterCount+32/*31+dirty bit*/)/32];
		Elem m_elems[ElemsInClusterCount];
		//rest bytes not specified
		/*void init()
		{ memset(m_paintBits,0,sizeof(m_paintBits));
		}*/
	} Cluster;
};

template<typename ClusterType_t> class AllocBlock
{ 
public:
	typedef ClusterType_t ClusterType;
	typedef typename ClusterType::Cluster Cluster;
	typedef typename ClusterType::Elem Elem;
private:
	Elem *m_first;
#ifdef MALLOC_FILO
	Elem *m_last;
#endif
	int m_freecount;
public:
#ifdef MALLOC_FREE_TEST
	int m_magic;
#endif
	AllocBlock *m_prev,*m_next;
	char m_data[(ClusterType::ClusterCount+1)*ClusterType::ClusterSize-4];
	Cluster *firstCluster()
	{ return (Cluster *)(((int)(void *)m_data)+(ClusterType::ClusterSize-1) & -ClusterType::ClusterSize); 
	}
	inline static AllocBlock *getAllocBlock(const void *elem) { return *(AllocBlock **)((int)elem & -ClusterType::ClusterSize); }
	static void link(AllocBlock *prev,AllocBlock *next) { prev->m_next=next; next->m_prev=prev; } 
	static AllocBlock *insert(AllocBlock *elem,AllocBlock *at) 
	{ elem->m_prev = at->m_prev;
		elem->m_next = at;
		at->m_prev->m_next = elem;
		at->m_prev	 = elem;
		return elem;
	} 
	AllocBlock();
	inline void *alloc()
	{ m_freecount--; 
		Elem *p=m_first; 
#ifdef MALLOC_WIPE
		if (m_freecount)
		{ ASSERT(((int *)m_first)[0]!=0x55555555)
			ASSERT(((int *)m_first)[1]==0x55555555)
		}
#endif
		m_first=*(Elem **)m_first;
#ifdef MALLOC_WIPE
		memset(p, 0x99, sizeof(Elem) );
#endif
		return p; 
	}
	inline bool free(void *e)
	{ 
#ifdef MALLOC_WIPE
		ASSERT(((int *)e)[1]!=0x55555555)
		memset(e, 0x55, sizeof(Elem) );
#endif
#ifdef MALLOC_FILO
		if (m_freecount) *(Elem **)m_last=(Elem *)e;
		m_last=(Elem *)e;
		if (isFull()) m_first=m_last;
#else
		*(Elem **)e=m_first; m_first=(Elem *)e; 
#endif
		m_freecount++; return isEmpty(); 
	}
	inline bool isEmpty() { return m_freecount==ClusterType::TotalElemCount; }
	inline bool isFull() { return m_freecount==0; }
	void unpaint()
	{ Cluster *c=firstCluster(), *ce=(Cluster *) ((int)c + ClusterType::ClusterSize*ClusterType::ClusterCount);
		while(c!=ce)
		{ if (c->m_paintBits[0]&1) // dirty bit
			{ memset(c->m_paintBits,0,sizeof(c->m_paintBits));
			}
			c= (Cluster *) ((int)c + ClusterType::ClusterSize);
		}
	}
#ifdef MALLOC_INTEGRITYCHECK
	void integrityCheck()
	{ 
#ifdef MALLOC_FREE_TEST
		if (m_magic!=0xabbad0d0)
		{ printf("Bad magic\n");
			DIV_BY_ZERO(__LINE__)
		}
#endif
		static int i=0;
		if (--i<0) { i=10; } else return;
		Elem **p=&m_first;
		for(int i=m_freecount;--i>=0;)
		{ ptr_check(p); 
#ifdef MALLOC_WIPE
			ASSERT(((int *)*p)[1]==0x55555555)
#endif
			p=(Elem **)*p;
		}
	}
	inline void ptr_check(Elem **p)
	{ int r=(int)(void *)*p-(int)m_data;
		if (r<0 || r>=sizeof(m_data) ) DIV_BY_ZERO(p)
		//if ( (r%sizeof(Elem))!=0 ) DIV_BY_ZERO(p)
		//if ( ((int *)*p)[1]!=0x77777777 || ((int *)*p)[2]!=0x77777777) DIV_BY_ZERO(p)  
	}
	inline void ptr_check() { ptr_check(&m_first); }
	~AllocBlock() { /*memset(this,0x55,sizeof(*this));*/ }
#endif
};

template<typename ClusterType>	AllocBlock<ClusterType>::AllocBlock():m_freecount(ClusterType::TotalElemCount)
{ 
	Elem *p;
	Cluster *c=firstCluster(), *ce=(Cluster *) ((int)c + ClusterType::ClusterSize*ClusterType::ClusterCount);
#ifdef MALLOC_FREE_TEST
	m_magic=0xabbad0d0;
#endif
	m_first = c->m_elems;
	while(c!=ce)
	{ //c->init();
		c->m_allocBlock=this;
		p=c->m_elems;
		for(int i=ClusterType::ElemsInClusterCount;--i>0;p++) 
		{
#ifdef MALLOC_WIPE
			((int *)p)[1]=0x55555555;
#endif
			*(Elem **)p=p+1;
		}
		c= (Cluster *) ((int)c + ClusterType::ClusterSize);
		*(Elem **)p=c->m_elems;
#ifdef MALLOC_WIPE
		((int *)p)[1]=0x55555555;
#endif
	}
#ifdef MALLOC_FILO
	m_last = p;
#endif
}

#ifdef MALLOC_EXCLUSIVENESS_TEST
extern int MEM_SEMA;
#define SEMA_ENTER ASSERT(++MEM_SEMA==1)
#define SEMA_LEAVE ASSERT(--MEM_SEMA==0)
#else
#define SEMA_ENTER
#define SEMA_LEAVE
#endif

template<typename AB > class BlockAllocator 
{ 
public:
	void *alloc();
	IF_MALLOC_INTEGRITYCHECK(void integrityCheck(int line=0);)
	void free(void *p);
	//enum { blockElemCount = 0x10000/sizeof(Elem), blockEntryCount = 0x10000, c_blockSize=blockElemCount*sizeof(Elem) };
	BlockAllocator():m_first(Create<AB>::aNew()),m_emptyBlockCount(1) { AB::link(m_first,m_first); } 
	typedef AB AllocBlock;
protected:
	AB *m_first; // first part of list is always with non-full blocks 
	int m_emptyBlockCount;
}; 

#ifdef MALLOC_INTEGRITYCHECK
template<typename AB> void BlockAllocator<AB>::integrityCheck(int line)
{ 
	AB *b=m_first;
	for(;;)
	{ if (b==0 || b->m_next->m_prev!=b || b->m_prev->m_next!=b) DIV_BY_ZERO(line)
		b->integrityCheck();
		b=b->m_next;
		if (b==m_first) break;
	}
}
#endif

template<typename AB> void *BlockAllocator<AB>::alloc()
{ 
	SEMA_ENTER
	IF_MALLOC_INTEGRITYCHECK(integrityCheck(__LINE__);)
#ifdef MALLOC_COUNT
	mcounts.block++;
#endif
	if (m_first->isEmpty()) m_emptyBlockCount--;
	void *p=m_first->alloc();
	if (m_first->isFull())
	{ m_first = m_first->m_next;
		if (m_first->isFull()) 
		{ m_first = AB::insert(Create<AB>::aNew(),m_first);
			m_emptyBlockCount++;
		}
	}
	SEMA_LEAVE
	return p;
}  

template<typename AB> void BlockAllocator<AB>::free(void *p)
{ 
	SEMA_ENTER
	IF_MALLOC_INTEGRITYCHECK(integrityCheck();)
#ifdef MALLOC_COUNT
	mcounts.block--;
#endif
	AB *b=AB::getAllocBlock(p);
#ifdef MALLOC_FREE_TEST
	if (b->m_magic!=0xabbad0d0)
	{ printf("Invalid free in Block Allocator\n");
		DIV_BY_ZERO(__LINE__)
	}
#endif
	if (b->isFull() && b!=m_first)
	{ AB::link(b->m_prev, b->m_next);
		m_first = AB::insert(b, m_first);
		b->free((typename AB::Elem *)p);
	}
	else if (b->free((typename AB::Elem *)p))
	{ if (m_emptyBlockCount>0)
		{ if (m_first == b) m_first = b->m_next; 
			AB::link(b->m_prev, b->m_next);
			delete b; 
		}
		else m_emptyBlockCount++;
	} 

	SEMA_LEAVE
}

template<int ElemSize, int ClusterCount, int ClusterSize> class BasicAllocator: 
	public BlockAllocator<AllocBlock<BasicClustering<ElemSize,ClusterCount,ClusterSize> > >
{
	//typedef BasicClustering<Elem,ClusterCount,ClusterSize> Clustering;
public:
	 BasicAllocator() {} // : BlockAllocator<AllocBlock<BasicClustering<Elem,ClusterCount,ClusterSize>> >()
};

template<typename Class, int ElemSize, int ClusterCount, int ClusterSize,int ElemsInClusterCount> class GCAllocator: 
	public BlockAllocator<AllocBlock<GCClustering<ElemSize,ClusterCount,ClusterSize, ElemsInClusterCount> > >
{
	
	typedef typename GCAllocator::AllocBlock AllocBlock;
	enum
	{ 
#ifdef MALLOC_FREE_TEST
		BufferSize=1
#else
		BufferSize=0x100000/ElemSize // 1MB
#endif
	};
	bool m_isFirstCall;
	int m_emptyCount;
	void *m_buffer[BufferSize];
public:
	Class *alloc() { return (Class *)BlockAllocator<AllocBlock>::alloc();}
	void free(void *p) { BlockAllocator<AllocBlock>::free(p); }
	void del(Class *p)
	{ p->~Class();
		free((void *)p); // this can create new unuses and new cleanups
	}
	bool paint(const Class *p);
	//bool isPainted(const Class *p);
	void unuse(Class *p)
	{ 
	ASSERT(p!=0 && ((int)p&3)==0);
#ifdef MALLOC_FREE_TEST
	if (AllocBlock::getAllocBlock(p)->m_magic!=0xabbad0d0)
	{ printf("Invalid unuse in Block Allocator\n");
		DIV_BY_ZERO(__LINE__)
	}
#endif
		m_buffer[--m_emptyCount]=p;
#ifdef MALLOC_COUNT
		mcounts.deletionCandidate++;
#endif
		if (m_emptyCount==0) cleanup();
	}
	void cleanup();
	GCAllocator(): BlockAllocator<AllocBlock>(),m_isFirstCall(true),m_emptyCount(BufferSize) { }
};

template<typename Class, int ES, int CC, int CS, int EICC> 
bool GCAllocator<Class, ES, CC, CS, EICC>::paint(const Class *a)
{ int av=(int)a;
	ASSERT(av!=0 && (av&3)==0);
#ifdef MALLOC_FREE_TEST
	if (AllocBlock::getAllocBlock(a)->m_magic!=0xabbad0d0)
	{ printf("Invalid paint in Block Allocator, with pointer: %p\n", a);
		DIV_BY_ZERO(__LINE__)
	}
#endif
	unsigned int *p = ((typename AllocBlock::Cluster *)(av & -CS))->m_paintBits;
	av-=AllocBlock::ClusterType::elemOffset;
	int offset= 1+(av&(CS-1))/ES;//todo: not to slow for elemsize=12?? (this size is not used however)
	*p|=1; // set dirty bit
	p+=offset/32;  
	int mask = (1<<(offset & 31));
	bool r= (*p & mask )== 0; // test bit
	*p |= mask; // set bit 
	return r; // returns whether first time painted
}

template<typename Class, int ES, int CC, int CS, int EICC> 
void GCAllocator<Class, ES, CC, CS, EICC>::cleanup()
{
	bool ifc=m_isFirstCall;
	//IF_MALLOC_VERBOSE_GC(TRACEP(i,ifc,"Cleanup { "))
	if (ifc)
	{ m_isFirstCall = false;
		{ AllocBlock *b=this->m_first;
			do {
				b->unpaint();
				b=b->m_next;
			} while (b!=this->m_first);
		}
		Class::GCStartPaint();
	}
	void **b=(void **)mstl_alloc(sizeof(m_buffer));
	{ // recurse until nothing left. This limits the amount of paint jobs
		int i=0;
		do
		{ void **bp=b;
#ifdef MALLOC_COUNT
			mcounts.deletionCandidate-=BufferSize-i;
#endif
			void **pbuf=m_buffer+BufferSize;
			void **pend=m_buffer+i;
			do // collect objects not painted:
			{ if (paint((Class *)*(--pbuf)))
				{ *bp=*pbuf;
					bp++;
				}
			} while(pbuf!=pend);
			m_emptyCount = BufferSize;
			for(void **p=b; p!=bp; p++)
			{ 
#ifdef MALLOC_FREE_TEST
				ASSERT(*(unsigned int *)*p>=0x10000000)
#endif
				del((Class *)*p);//this can generate new cleanups, but this should not be a problem
			} 
			i = m_emptyCount;
		} while (i<BufferSize);
	}
	mstl_free(b);
	//IF_MALLOC_VERBOSE_GC(TRACEF("} Cleanup "))
	if (ifc)
	{ m_isFirstCall = true;
	}

}

}

#endif /* __MSTL_ALLOC_H__ */

